# There are two sorted arrays nums1 and nums2 of size m and n respectively.
#
# Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
#
# You may assume nums1 and nums2 cannot be both empty.
#
# Example 1:
#
# nums1 = [1, 3]
# nums2 = [2]
#
# The median is 2.0
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        i = 0
        j = 0
        isInt = False
        isFloat = False
        l1 = len(nums1)
        l2 = len(nums2)
        mid = (l1 + l2) / 2
        nums3 = []

        # 对一些特殊情况做处理
        if l1 == 0 and l2 == 0:
            return 0

        # 判断nums1和nums2总的元素个数是奇数还是偶数
        if mid.is_integer():
            isInt = True
        else:
            isFloat = True

        # 这里还是使用了有序表的合并算法。
        # 在第2题，Add Two Numbers题目中我也使用了这个算法
        while i < l1 and j < l2:
            if nums1[i] < nums2[j]:
                nums3.append(nums1[i])
                i += 1
            else:
                nums3.append(nums2[j])
                j += 1

            if len(nums3) > mid:
                break

        # 循环结束或者跳出循环后看哪个数组有剩余元素,在num3数组没有达到要求
        # （这个要求就是要让他的长度越过中间的1个或2个元素）时，继续往里面加入元素。
        if i < l1:
            while len(nums3) <= mid:
                nums3.append(nums1[i])
                i += 1
        if j < l2:
            while len(nums3) <= mid:
                nums3.append(nums2[j])
                j += 1

        if isInt:
            return (nums3[-1] + nums3[-2]) / 2
        if isFloat:
            return nums3[-1]


# 这个算法时间复杂度上比较差，处于第二队列(150ms)的中等水平（我在160-200ms）
# 第一队列的时间复杂度在100ms左右。
# 要求的时间复杂度是 O(log (m+n)).-->从这个要求中可以看出我的时间复杂度应该是O(m+n)
# 因为采用了对mid之前半个元素表进行了遍历。
# 而更快的方法应该是从mid入手，直接找中间的那个元素或者2个元素。

s = Solution()
result = s.findMedianSortedArrays([], [])
print(result)
